P2515 [HAOI2010]软件安装

十分巧妙的一道缩点+dfs序上背包好题

题解

容易发现一个强联通分量里的所有点都是相互依存的，也就是说一个选，个个选，所以不妨把代价、贡献分别求和并缩点

缩完点后是个有着森林性质的有向图，自然的，加个虚点，把所有树根连在一起，合成一棵树

接下来的操作就十分玄学巧妙了，是复杂度十分优秀的dfs序dp（我是第一次见到。。。）

先跑出这棵树的dfs序，并处理出一些东西

记$id[i]$表示dfs序第i位的节点编号，$sz[i]表示以i为根的子树的大小$，$cost[i]$为节点的代价，$val[i]$为节点的贡献，$pre[i]$表示树上，根到i父亲的代价的和

设$f[i][j]$表示dfs序上，前i-1个点（注意，这是精华所在），用了j单位内存时的最大价值

转移分成两类，采用刷表法

  1. 选择当前节点
  1. 不选择当前节点

最后答案就是$f[新树节点数+1][m]$

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=105,M=505;
int f[N][M],n,m,du[N],id[N],sz[N],cn,en,h[N],dfn[N],cnt,low[N],st[N],lim,scc[N],cost[N],val[N],w[N],s[N],pre[N];
bool v[N];

struct edge{
    int n,u,v;
}e[N<<1];

void add(int x,int y){
    e[++en]=(edge){h[x],x,y};
    h[x]=en;
}

void tarjan(int x){
    low[x]=dfn[x]=++cnt;
    st[++lim]=x;
    v[x]=1;
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else{
            if(v[y]) low[x]=min(low[x],dfn[y]);
        }
    }
    if(low[x]==dfn[x]){
        int top;
        cn++;
        for(;;){
            top=st[lim--];
            v[top]=0;
            scc[top]=cn;
            cost[cn]+=w[top];
            val[cn]+=s[top];
            if(top==x) break;
        }
    }
}

void dfs(int x){
    id[++cnt]=x;
    sz[x]=1;
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        pre[y]=pre[x]+cost[x];
        dfs(y);
        sz[x]+=sz[y];
    }
}

signed main(){
    read(n);read(m);
    for(int i=1;i<=n;i++) read(w[i]);
    for(int i=1;i<=n;i++) read(s[i]);
    for(int i=1,x;i<=n;i++){
        read(x);
        if(x) add(x,i);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    memset(h,0,sizeof h);
    int enn=en;
    for(int i=1;i<=enn;i++){
        int x=e[i].u,y=e[i].v;
        if(scc[x]==scc[y]) continue;
        add(scc[x],scc[y]);
        du[scc[y]]++;
    }
    for(int i=1;i<=cn;i++) if(!du[i]) add(0,i); //加虚点
    cnt=0;
    dfs(0);
    for(int i=1;i<=cnt;i++){
        for(int j=pre[id[i]];j<=m-cost[id[i]];j++) //选
            f[i+1][j+cost[id[i]]]=max(f[i+1][j+cost[id[i]]],f[i][j]+val[id[i]]);
        for(int j=pre[id[i]];j<=m;j++) //不选
            f[i+sz[id[i]]][j]=max(f[i+sz[id[i]]][j],f[i][j]);
    }
    write(f[cnt+1][m]);
}
赏

fighter